iT邦幫忙

第 11 屆 iThome 鐵人賽
DAY 13
0
自我挑戰組

練習程式系列 第 13 篇

java，Bubble sort algorithm 和c++， Insertion Sort 、Selection Sort

11th鐵人賽
1246 瀏覽

  • 分享至 

  • xImage
    •  

看網路上大大們的文章和影片，做些紀錄。
以下內容來自網路上大大們的文章。
紀錄排序的程式來源。 稍微修改，print 觀察

Bubble sort algorithm

教學來源:Bubble sort algorithm

程式來源:Bubble Sort 氣泡演算法 Java實作

最慢的版本:

class BubbleSort {
 public static void main(String[] args) {
  int[] test = new int[]{3,1,3,2,5,4,9,8,4,2,5,2};
  int[] a = sort(test);
  for (int t: a) {
   System.out.printf("result:%d,", t);
  }
 }

 static int[] sort(int[] input) {
  int loopcount = 0; //迴圈跑幾次
  int count = 0; //交換次數
  int length = input.length; //要排列的數字長度
  int temp; //前面數字>後面數字時兩個會互換位置,此時需要此變數

  for (int i = 0; i < length; i++) {
   for (int j = 0; j < length - 1; j++) {
    loopcount++;
    System.out.printf("迴圈次數:%d\n", loopcount);
    //比大小,if 前>後 換位
    if (input[j] > input[j + 1]) {
     temp = input[j]; //前面數字先存到變數
     input[j] = input[j + 1]; //後面數字取代前面數字
     input[j + 1] = temp; //將變數(前面數字)存到後面變數
     count++;
     System.out.printf("count:%d-->", count); //印出交換的次數
     for (int a: input) {
      System.out.printf("%d,", a);
     }
     System.out.println();
    }
   }

  }
  return input;
 }
}

迴圈次數:1
count:1-->1,3,3,2,5,4,9,8,4,2,5,2,
迴圈次數:2
迴圈次數:3
count:2-->1,3,2,3,5,4,9,8,4,2,5,2,
迴圈次數:4
迴圈次數:5
count:3-->1,3,2,3,4,5,9,8,4,2,5,2,
迴圈次數:6
迴圈次數:7
count:4-->1,3,2,3,4,5,8,9,4,2,5,2,
迴圈次數:8
count:5-->1,3,2,3,4,5,8,4,9,2,5,2,
迴圈次數:9
count:6-->1,3,2,3,4,5,8,4,2,9,5,2,
迴圈次數:10
count:7-->1,3,2,3,4,5,8,4,2,5,9,2,
迴圈次數:11
count:8-->1,3,2,3,4,5,8,4,2,5,2,9,
迴圈次數:12
迴圈次數:13
count:9-->1,2,3,3,4,5,8,4,2,5,2,9,
迴圈次數:14
迴圈次數:15
迴圈次數:16
迴圈次數:17
迴圈次數:18
count:10-->1,2,3,3,4,5,4,8,2,5,2,9,
迴圈次數:19
count:11-->1,2,3,3,4,5,4,2,8,5,2,9,
迴圈次數:20
count:12-->1,2,3,3,4,5,4,2,5,8,2,9,
迴圈次數:21
count:13-->1,2,3,3,4,5,4,2,5,2,8,9,
迴圈次數:22
迴圈次數:23
迴圈次數:24
迴圈次數:25
迴圈次數:26
迴圈次數:27
迴圈次數:28
count:14-->1,2,3,3,4,4,5,2,5,2,8,9,
迴圈次數:29
count:15-->1,2,3,3,4,4,2,5,5,2,8,9,
迴圈次數:30
迴圈次數:31
count:16-->1,2,3,3,4,4,2,5,2,5,8,9,
迴圈次數:32
迴圈次數:33
迴圈次數:34
迴圈次數:35
迴圈次數:36
迴圈次數:37
迴圈次數:38
迴圈次數:39
count:17-->1,2,3,3,4,2,4,5,2,5,8,9,
迴圈次數:40
迴圈次數:41
count:18-->1,2,3,3,4,2,4,2,5,5,8,9,
迴圈次數:42
迴圈次數:43
迴圈次數:44
迴圈次數:45
迴圈次數:46
迴圈次數:47
迴圈次數:48
迴圈次數:49
count:19-->1,2,3,3,2,4,4,2,5,5,8,9,
迴圈次數:50
迴圈次數:51
count:20-->1,2,3,3,2,4,2,4,5,5,8,9,
迴圈次數:52
迴圈次數:53
迴圈次數:54
迴圈次數:55
迴圈次數:56
迴圈次數:57
迴圈次數:58
迴圈次數:59
count:21-->1,2,3,2,3,4,2,4,5,5,8,9,
迴圈次數:60
迴圈次數:61
count:22-->1,2,3,2,3,2,4,4,5,5,8,9,
迴圈次數:62
迴圈次數:63
迴圈次數:64
迴圈次數:65
迴圈次數:66
迴圈次數:67
迴圈次數:68
迴圈次數:69
count:23-->1,2,2,3,3,2,4,4,5,5,8,9,
迴圈次數:70
迴圈次數:71
count:24-->1,2,2,3,2,3,4,4,5,5,8,9,
迴圈次數:72
迴圈次數:73
迴圈次數:74
迴圈次數:75
迴圈次數:76
迴圈次數:77
迴圈次數:78
迴圈次數:79
迴圈次數:80
迴圈次數:81
count:25-->1,2,2,2,3,3,4,4,5,5,8,9,
迴圈次數:82
迴圈次數:83
迴圈次數:84
迴圈次數:85
迴圈次數:86
迴圈次數:87
迴圈次數:88
迴圈次數:89
迴圈次數:90
迴圈次數:91
迴圈次數:92
迴圈次數:93
迴圈次數:94
迴圈次數:95
迴圈次數:96
迴圈次數:97
迴圈次數:98
迴圈次數:99
迴圈次數:100
迴圈次數:101
迴圈次數:102
迴圈次數:103
迴圈次數:104
迴圈次數:105
迴圈次數:106
迴圈次數:107
迴圈次數:108
迴圈次數:109
迴圈次數:110
迴圈次數:111
迴圈次數:112
迴圈次數:113
迴圈次數:114
迴圈次數:115
迴圈次數:116
迴圈次數:117
迴圈次數:118
迴圈次數:119
迴圈次數:120
迴圈次數:121
迴圈次數:122
迴圈次數:123
迴圈次數:124
迴圈次數:125
迴圈次數:126
迴圈次數:127
迴圈次數:128
迴圈次數:129
迴圈次數:130
迴圈次數:131
迴圈次數:132
1,2,2,2,3,3,4,4,5,5,8,9,

因為bubblesort每一輪都把最大的數往右邊移，所以右邊都是排序好的，不用在比較，只要改成j < length-1-i
，迴圈次數剛好會是原本的一半:

class BubbleSort {
 public static void main(String[] args) {
  int[] test = new int[]{3,1,3,2,5,4,9,8,4,2,5,2};
  int[] a = sort(test);
  for (int t: a) {
   System.out.printf("%d,", t);
  }
 }


 static int[] sort(int[] input) {
  int loopcount = 0;
  int count = 0;
  int length = input.length;
  int temp;

  for (int i = 0; i < length; i++) {
   for (int j = 0; j < length - 1 - i; j++) {
    loopcount++;
    System.out.printf("迴圈次數:%d\n", loopcount);
    if (input[j] > input[j + 1]) {
     temp = input[j];
     input[j] = input[j + 1];
     input[j + 1] = temp;
     count++;
     System.out.printf("count:%d-->", count);
     for (int a: input) {
      System.out.printf("%d,", a);
     }
     System.out.println();
    }
   }
  }
  return input;
 }
}

迴圈次數:1
count:1-->1,3,3,2,5,4,9,8,4,2,5,2,
迴圈次數:2
迴圈次數:3
count:2-->1,3,2,3,5,4,9,8,4,2,5,2,
迴圈次數:4
迴圈次數:5
count:3-->1,3,2,3,4,5,9,8,4,2,5,2,
迴圈次數:6
迴圈次數:7
count:4-->1,3,2,3,4,5,8,9,4,2,5,2,
迴圈次數:8
count:5-->1,3,2,3,4,5,8,4,9,2,5,2,
迴圈次數:9
count:6-->1,3,2,3,4,5,8,4,2,9,5,2,
迴圈次數:10
count:7-->1,3,2,3,4,5,8,4,2,5,9,2,
迴圈次數:11
count:8-->1,3,2,3,4,5,8,4,2,5,2,9,
迴圈次數:12
迴圈次數:13
count:9-->1,2,3,3,4,5,8,4,2,5,2,9,
迴圈次數:14
迴圈次數:15
迴圈次數:16
迴圈次數:17
迴圈次數:18
count:10-->1,2,3,3,4,5,4,8,2,5,2,9,
迴圈次數:19
count:11-->1,2,3,3,4,5,4,2,8,5,2,9,
迴圈次數:20
count:12-->1,2,3,3,4,5,4,2,5,8,2,9,
迴圈次數:21
count:13-->1,2,3,3,4,5,4,2,5,2,8,9,
迴圈次數:22
迴圈次數:23
迴圈次數:24
迴圈次數:25
迴圈次數:26
迴圈次數:27
count:14-->1,2,3,3,4,4,5,2,5,2,8,9,
迴圈次數:28
count:15-->1,2,3,3,4,4,2,5,5,2,8,9,
迴圈次數:29
迴圈次數:30
count:16-->1,2,3,3,4,4,2,5,2,5,8,9,
迴圈次數:31
迴圈次數:32
迴圈次數:33
迴圈次數:34
迴圈次數:35
迴圈次數:36
count:17-->1,2,3,3,4,2,4,5,2,5,8,9,
迴圈次數:37
迴圈次數:38
count:18-->1,2,3,3,4,2,4,2,5,5,8,9,
迴圈次數:39
迴圈次數:40
迴圈次數:41
迴圈次數:42
迴圈次數:43
count:19-->1,2,3,3,2,4,4,2,5,5,8,9,
迴圈次數:44
迴圈次數:45
count:20-->1,2,3,3,2,4,2,4,5,5,8,9,
迴圈次數:46
迴圈次數:47
迴圈次數:48
迴圈次數:49
count:21-->1,2,3,2,3,4,2,4,5,5,8,9,
迴圈次數:50
迴圈次數:51
count:22-->1,2,3,2,3,2,4,4,5,5,8,9,
迴圈次數:52
迴圈次數:53
迴圈次數:54
count:23-->1,2,2,3,3,2,4,4,5,5,8,9,
迴圈次數:55
迴圈次數:56
count:24-->1,2,2,3,2,3,4,4,5,5,8,9,
迴圈次數:57
迴圈次數:58
迴圈次數:59
迴圈次數:60
count:25-->1,2,2,2,3,3,4,4,5,5,8,9,
迴圈次數:61
迴圈次數:62
迴圈次數:63
迴圈次數:64
迴圈次數:65
迴圈次數:66
1,2,2,2,3,3,4,4,5,5,8,9,

可以再繼續減少迴圈，如果是全部排序好的陣列，根本就不用在比較了:

class BubbleSort {
	public static void main(String[] args) {
		int[] test = new int[]{3,1,3,2,5,4,9,8,4,2,5,2};
		int[] a= sort(test);
		for(int t:a){
          System.out.printf("%d,",t);
		}
	}

  static int[] sort(int[] input){
      Boolean is_sorted;//如果是true，就代表陣列的值早就排好順序了，也就不用再跑迴圈了

      int loopcount =0; 
      int count = 0; 
	   	int length = input.length;
	    int temp;
	    for(int i=0;i<length;i++){
	    	is_sorted = true;
	    	for(int j=0;j<length-1-i;j++){
           loopcount++;
           System.out.printf("迴圈次數:%d\n",loopcount);
	    	   if(input[j]>input[j+1]){
	    		   temp = input[j];
	    		   input[j] = input[j+1];
	    		   input[j+1] = temp; 
	    		   count++;
		    	   System.out.printf("count:%d-->",count);
		         for(int a:input){
                System.out.printf("%d,",a);
		    	   }
		    	   System.out.println();
	    		   is_sorted = false;
	    	   }
	    	}
        if (is_sorted) break;
	    }
		return input;
  }
}

圈次數:1
count:1-->1,3,3,2,5,4,9,8,4,2,5,2,
迴圈次數:2
迴圈次數:3
count:2-->1,3,2,3,5,4,9,8,4,2,5,2,
迴圈次數:4
迴圈次數:5
count:3-->1,3,2,3,4,5,9,8,4,2,5,2,
迴圈次數:6
迴圈次數:7
count:4-->1,3,2,3,4,5,8,9,4,2,5,2,
迴圈次數:8
count:5-->1,3,2,3,4,5,8,4,9,2,5,2,
迴圈次數:9
count:6-->1,3,2,3,4,5,8,4,2,9,5,2,
迴圈次數:10
count:7-->1,3,2,3,4,5,8,4,2,5,9,2,
迴圈次數:11
count:8-->1,3,2,3,4,5,8,4,2,5,2,9,
迴圈次數:12
迴圈次數:13
count:9-->1,2,3,3,4,5,8,4,2,5,2,9,
迴圈次數:14
迴圈次數:15
迴圈次數:16
迴圈次數:17
迴圈次數:18
count:10-->1,2,3,3,4,5,4,8,2,5,2,9,
迴圈次數:19
count:11-->1,2,3,3,4,5,4,2,8,5,2,9,
迴圈次數:20
count:12-->1,2,3,3,4,5,4,2,5,8,2,9,
迴圈次數:21
count:13-->1,2,3,3,4,5,4,2,5,2,8,9,
迴圈次數:22
迴圈次數:23
迴圈次數:24
迴圈次數:25
迴圈次數:26
迴圈次數:27
count:14-->1,2,3,3,4,4,5,2,5,2,8,9,
迴圈次數:28
count:15-->1,2,3,3,4,4,2,5,5,2,8,9,
迴圈次數:29
迴圈次數:30
count:16-->1,2,3,3,4,4,2,5,2,5,8,9,
迴圈次數:31
迴圈次數:32
迴圈次數:33
迴圈次數:34
迴圈次數:35
迴圈次數:36
count:17-->1,2,3,3,4,2,4,5,2,5,8,9,
迴圈次數:37
迴圈次數:38
count:18-->1,2,3,3,4,2,4,2,5,5,8,9,
迴圈次數:39
迴圈次數:40
迴圈次數:41
迴圈次數:42
迴圈次數:43
count:19-->1,2,3,3,2,4,4,2,5,5,8,9,
迴圈次數:44
迴圈次數:45
count:20-->1,2,3,3,2,4,2,4,5,5,8,9,
迴圈次數:46
迴圈次數:47
迴圈次數:48
迴圈次數:49
count:21-->1,2,3,2,3,4,2,4,5,5,8,9,
迴圈次數:50
迴圈次數:51
count:22-->1,2,3,2,3,2,4,4,5,5,8,9,
迴圈次數:52
迴圈次數:53
迴圈次數:54
count:23-->1,2,2,3,3,2,4,4,5,5,8,9,
迴圈次數:55
迴圈次數:56
count:24-->1,2,2,3,2,3,4,4,5,5,8,9,
迴圈次數:57
迴圈次數:58
迴圈次數:59
迴圈次數:60
count:25-->1,2,2,2,3,3,4,4,5,5,8,9,
迴圈次數:61
迴圈次數:62
迴圈次數:63
1,2,2,2,3,3,4,4,5,5,8,9,

Insertion Sort

參考：
Comparison Sort: Insertion Sort(插入排序法)

照抄：

#include <iostream>

class Insertion {
  public: void InsertionSort(int * arr, int size) {

    for (int i = 1; i < size; i++) {
      int key = arr[i];
      int j = i - 1;
      while (key < arr[j] && j >= 0) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
      std::cout << "process:\n";
      PrintArray(arr, 6);
    }
  }
  public: void PrintArray(int * arr, int size) {
    for (int i = 0; i < size; i++) {
      std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
  }
};
int main() {
  Insertion insertion;
  int array[6] = { 5, 3, 1, 2, 6, 4 };
  std::cout << "original:\n";
  insertion.PrintArray(array, 6);

  insertion.InsertionSort(array, 6);
  std::cout << "sorted:\n";
  insertion.PrintArray(array, 6);

  int array1[6] = { 1,2,3,4,5,6 };
  std::cout << "original:\n";
  insertion.PrintArray(array1, 6);

  insertion.InsertionSort(array1, 6);
  std::cout << "sorted:\n";
  insertion.PrintArray(array1, 6);
  return 0;
}

結果：

original:
5 3 1 2 6 4
process:
3 5 1 2 6 4
process:
1 3 5 2 6 4
process:
1 2 3 5 6 4
process:
1 2 3 5 6 4
process:
1 2 3 4 5 6
sorted:
1 2 3 4 5 6



original:
1 2 3 4 5 6
process:
1 2 3 4 5 6
process:
1 2 3 4 5 6
process:
1 2 3 4 5 6
process:
1 2 3 4 5 6
process:
1 2 3 4 5 6
sorted:
1 2 3 4 5 6

Selection Sort

參考：選擇排序法(Selection Sort)

照抄：

#include <iostream>

class Selection {
  public: void SelectionSort(int * arr, int size) {
    for (int i = 0, minIndex; i < size - 1; i++) {
      minIndex = i;
      for (int j = i + 1; j < size; j++)
        if (arr[j] < arr[minIndex])
          minIndex = j;
      if (minIndex != i)
        std::swap(arr[minIndex], arr[i]);
      std::cout << "process:\n";
      PrintArray(arr, 6);
    }
  }
  public: void PrintArray(int * arr, int size) {
    for (int i = 0; i < size; i++) {
      std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
  }
};
int main() {
  Selection selection;
  int array[6] = { 5, 3, 1, 2, 6, 4 };
  std::cout << "original:\n";
  selection.PrintArray(array, 6);

  selection.SelectionSort(array, 6);
  std::cout << "sorted result:\n";
  selection.PrintArray(array, 6);
}

結果：

original:
5 3 1 2 6 4
process:
1 3 5 2 6 4
process:
1 2 5 3 6 4
process:
1 2 3 5 6 4
process:
1 2 3 4 6 5
process:
1 2 3 4 5 6
sorted:
1 2 3 4 5 6

上一篇
java，雙向連結串列
下一篇
java，quicksort、Counting Sort和c++ ，mergesort、Heap Sort和 js ，Shell Sort、Radix Sort
系列文
練習程式 共 37 篇
  1. 33
    Android ，存圖片到SQLite，process、thread、ByteArrayOutputStream
  2. 34
    Android 畫面、delete image、Apache（php） , 安裝apache,import library
  3. 35
    WEB 筆記
  4. 36
    Android，Navigation
  5. 37
    C# 筆記
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22203 篇
完賽人數
602 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙